package com.study.lu.动态规划;

public class 跳跃游戏2 {
    /**
     * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
     * <p>
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * <p>
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * <p>
     * 假设你总是可以到达数组的最后一个位置。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        //int[] nums = new int[]{3, 2, 1, 0, 4};
        // int[] nums = new int[]{0, 1};

        //int[] nums = new int[]{1, 2};
        int steps = jump(nums);

        int steps2 = jump2(nums);
        System.out.println(steps);
        System.out.println(steps2);

    }

    private static int jump2(int[] nums) {
        int pos = nums.length - 1;
        int step = 0;
        // 每步的最大结束位置
        int end = 0;
        int maxPos = 0;
        for (int i = 0; i < pos; i++) {
            // 找到坐标为i上最大能到的坐标
            maxPos = Math.max(maxPos, i + nums[i]);
            // 如果这个坐标刚好等于每步的最大结束位置
            if (i == end) {
                step++;
                end = maxPos;
            }

        }
        return step;
    }

    private static int jump(int[] nums) {
        // 从数组尾部开始，反推，用的步数越少越好，那么相应的就是离数组尾部越远越好
        int pos = nums.length - 1;
        int step = 0;
        // 从数组尾部开始
        while (pos > 0) {
            for (int i = 0; i < pos; i++) {
                // 如果坐标i+坐标i上的值刚好等于pos
                // 从左到右，用的步数最小（坐标上值小的能到达的位置，坐标上值大的也能到达）
                if (i + nums[i] >= pos) {
                    pos = i;
                    step++;
                    break;
                }
            }
        }

        return step;

    }
}
